// 1971. 寻找图中是否存在路径
/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number} source
 * @param {number} destination
 * @return {boolean}
 */
// 广度优先搜索
var validPath = function (n, edges, source, destination) {
	const adj = new Array(n).fill(0).map(() => new Array())
	for (const edge of edges) {
		const x = edge[0],
			y = edge[1]
		adj[x].push(y)
		adj[y].push(x)
	}
	const visited = new Array(n).fill(false)
	const queue = [source]
	visited[source] = true
	while (queue.length) {
		const vertex = queue.shift()
		if (vertex === destination) {
			break
		}
		for (const next of adj[vertex]) {
			if (!visited[next]) {
				queue.push(next)
				visited[next] = true
			}
		}
	}
	return visited[destination]
}
// 深度优先搜索
var validPath = function (n, edges, source, destination) {
	const adj = new Array(n).fill(0).map(() => new Array())
	for (const edge of edges) {
		const x = edge[0],
			y = edge[1]
		adj[x].push(y)
		adj[y].push(x)
	}
	const visited = new Array(n).fill(false)
	return dfs(source, destination, adj, visited)
}
const dfs = (source, destination, adj, visited) => {
	if (source === destination) return true
	visited[source] = true
	for (const next of adj[source]) {
		if (!visited[next] && dfs(next, destination, adj, visited)) {
			return true
		}
	}
	return false
}
// 并查集
var validPath = function (n, edges, source, destination) {
	if (source === destination) {
		return true
	}
	const uf = new UnionFind(n)
	for (const edge of edges) {
		uf.uni(edge[0], edge[1])
	}
	return uf.connect(source, destination)
}
class UnionFind {
	constructor(n) {
		this.parent = new Array(n).fill(0).map((_, i) => i)
		this.rank = new Array(n).fill(0)
	}
	uni(x, y) {
		const rootx = this.find(x)
		const rooty = this.find(y)
		if (rootx !== rooty) {
			if (this.rank[rootx] > this.rank[rooty]) {
				this.parent[rooty] = rootx
			} else if (this.rank[rootx] < this.rank[rooty]) {
				this.parent[rootx] = rooty
			} else {
				this.parent[rooty] = rootx
				this.rank[rootx]++
			}
		}
	}
	find(x) {
		if (this.parent[x] !== x) {
			this.parent[x] = this.find(this.parent[x])
		}
		return this.parent[x]
	}
	connect(x, y) {
		return this.find(x) === this.find(y)
	}
}
const res = validPath(
	10,
	[
		[4, 3],
		[1, 4],
		[4, 8],
		[1, 7],
		[6, 4],
		[4, 2],
		[7, 4],
		[4, 0],
		[0, 9],
		[5, 4],
	],
	5,
	9
)
console.log('validPath :>>', res)
